package com.cuz.daileetcode.bat100;

public class 物品只有一个指定容量装满背包的最大价值 {
    public static void main(String[] args) {
        int[] volume = {2, 2, 3, 4, 5, 6};
        int[] value = {2, 2, 4, 7, 1, 100};
        System.out.println(solution1(volume, value, 5));
    }

    public static int solution1(int[] volume, int[] value, int v) {
        int things = value.length;
        int[][] dp = new int[things][v + 1];
        //这个背包允许我们装以下第一个物品
        if (v >= volume[0]) {
            //选择0~0位置物品 凑出的体积只能是volume[0]
            dp[0][volume[0]] = value[0];
        }
        for (int row = 1; row < things; row++) {
            for (int col = 0; col <= v; col++) {
                //不选择当前物品 也就是说0~row-1 物品随便选择的最大价值
                dp[row][col] = dp[row - 1][col];
                //当前位置的体积允许我们选择它
                if (col - volume[row] >= 0) {
                    int chooseCurThing =
                            //0~row物品随便选 体积需要是col - volume[row]
                            //这样我们装上当前物品才能刚刚好装满体积col
                            //之前物品的价值+当前物品价值 就是选择当前物品的最大价值
                            dp[row][col - volume[row]] + value[row];
                    //取大者
                    dp[row][col] = Math.max(dp[row][col], chooseCurThing);
                }
            }
        }
        return dp[things - 1][v] == 0 ? -1:dp[things - 1][v];
    }

}
